/*************************************************************************
	> File Name: 102.二叉树的层序遍历.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 三  9/15 12:39:21 2021
 ************************************************************************/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
//1.判断一层结束:先统计当前队列的元素个数，将当前的所有元素出队，这些元素都在同一层。同一层结束后进行下一次迭代，迭代次数就是层数
//2.每层的节点个数：当前队列中的元素个数
//returnSize记录结果中二维数组的行数，returnColumnSizes记录每行的个数
#define max 1024
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    //队列存放树节点
    struct TreeNode *queue[max]; //静态数组
    int head = 0, tail = 0;

    int **ans = malloc(sizeof(int *) * max);
    *returnColumnSizes = malloc(sizeof(int) * max);

    int level = 0, count = 0; //level为层数
    queue[tail++] = root; //根节点入队
    count++;

    while (head != tail) {
        count = tail - head; //当前队列中的元素个数
        (*returnColumnSizes)[level] = count; //记录当前层的元素个数
        //存储当前层的元素
        ans[level] = malloc(sizeof(int) * count);
        //相比于普通的队列出队，这里是将同一层的元素全部出队
        for (int i = 1; i <= count; i++) { //出队同一层的元素
            struct TreeNode *p = queue[head++];
            ans[level][i - 1] = p->val;
            if (p->left) queue[tail++] = p->left; //入队刚刚出队元素的左孩子子结点
            if (p->right) queue[tail++] = p->right;
        }
        level++;
    }
    *returnSize = level; //记录总的层数
    return ans;
}
